/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-08-23
 * Time: 19:12
 */
import java.util.Arrays;

public class MinArrayWeight {

    // 辅助函数，用于计算数组的权值
    private static int calculateWeight(int[] arr) {
        int weight = 0;
        for (int i = 1; i < arr.length; i++) {
            weight += Math.abs(arr[i] - arr[i - 1]);
        }
        return weight;
    }

    // 尝试插入额外数字并计算最小权值（这里使用简单的贪心策略）
    public static int minWeightAfterInsertion(int[] nums, int m) {
        // 复制一份原始数组，以避免修改它
        int[] sortedNums = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sortedNums); // 对复制后的数组进行排序，以便更容易地插入数字

        // 创建一个足够大的数组来存储结果
        int[] result = new int[nums.length + m];


        // 插入额外数字（这里使用一种简单的贪心策略：尽可能均匀地插入）
        int index = 0;
        int additional = 1; // 额外的数字从1开始
        int interval = (nums.length + m - 1) / nums.length; // 理想情况下，每对相邻原始数字之间应该插入多少个额外数字

        for (int num : sortedNums) {
            result[index++] = num;

            // 尝试在原始数字之间插入额外数字
            for (int i = 0; i < interval && m > 0; i++, m--) {
                result[index++] = additional++;
            }

            // 如果还有剩余的额外数字需要插入，并且不是在最后一个原始数字之后
            // 我们可以将它们添加到数组的末尾（注意：这不一定总是最优的）
            if (m > 0 && index < result.length) {
                result[index++] = additional++;
                m--;
            }

            // 调整interval，因为最后一段可能不需要插入这么多额外数字
            if (m == 0) {
                interval = 0;
            }
        }

        // 如果在遍历原始数字后还有额外的数字没有插入（这通常不会发生，除非interval计算错误）
        // 我们可以将它们添加到数组的末尾（但这在上面的循环中已经被处理了）

        // 计算并返回结果数组的权值
        return calculateWeight(result);
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int m = 3;
        System.out.println(minWeightAfterInsertion(nums, m)); // 输出可能是接近但不一定是最小的权值
    }
}